#include <iostream>
#include <cstdlib>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode;

class LList
{
private:
	LNode *head;
public:
	LList();
	Status InitList();
	Status DestroyList();
	Status ClearList();
	Status ListEmpty();
	int ListLength();
	ElemType GetElem(int i);
	int LocateElem(ElemType e, bool (*)(ElemType, ElemType));
	ElemType PriorElem(ElemType cur_e);
	ElemType NextElem(ElemType cur_e);
	Status ListInsert(ElemType e, int i);
	ElemType ListDelete(int i);
	Status ListTraverse(void (*func)(ElemType));
	Status ListReverse()
	{
		LNode *p, *t, *q;
		q = this->head->next;
		p = q->next;
		if(!p)
			return OK;
		t = p->next;
		q->next = NULL;
		while(t)
		{
			p->next = q;
			q = p;
			p = t;
			t = t->next;
		}
		p->next = q;
		this->head->next = p;
		return OK;
	}
};

LList::LList()
{
	InitList();
}

Status LList::InitList()
{
	this->head = (LNode *)malloc(sizeof(LNode));
	this->head->next = NULL;
	return OK;
}

Status LList::DestroyList()
{
	LNode *p = this->head->next, *q;
	while(p)
	{
		q = p;
		p = p -> next;
		std::cout << "free " << q->data << std::endl;
		free(q);
	}
	this->head->next = NULL;
	return OK;
}

Status LList::ClearList()
{
	return this->DestroyList();
}

Status LList::ListEmpty()
{
	return (this->head->next == NULL);
}

int LList::ListLength()
{
	LNode *p = this->head;
	int length = 0;
	while(p->next)
	{
		p = p->next;
		length++;
	}
	return length;
}

int LList::LocateElem(ElemType e, bool (*func)(ElemType, ElemType))
{
	LNode *p = this->head->next;
	int count = 1;
	while(p)
	{
		if((*func)(p->data, e))
			break;
		p = p->next;
		count++;
	}
	if(!p)
		return 0;
	else
		return count;
}

ElemType LList::PriorElem(ElemType cur_e)
{
	LNode *p = this->head->next;
	if(p -> data == cur_e)
		exit(ERROR);
	while(p->next)
	{
		if(p->next->data == cur_e)
			return p->data;
		p = p->next;
	}
	if(!p->next)
		exit(ERROR);
	return ERROR;
}

ElemType LList::NextElem(ElemType cur_e)
{
	LNode *p = this->head->next;
	while(p->next)
	{
		if(p->data == cur_e)
			return p->next->data;
		p = p->next;
	}
	if(!p->next)
		exit(ERROR);
	return ERROR;
}

ElemType LList::GetElem(int i)
{
	LNode *p = this->head->next;
	int j;
	for(j = 1; p && j < i; j++)
		p = p->next;
	if(!p || j>i)
		return ERROR;
	return p->data;
}



Status LList::ListInsert(ElemType e, int i)
{
	LNode *p = (this->head), *s;
	int j;
	for(j = 0; p && j < i-1; j++)
		p = p->next;
	if(!p || j > i-1)
		return ERROR;
	s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

ElemType LList::ListDelete(int i)
{
	LNode *p = (this->head), *q;
	ElemType t;
	int j;
	for(j = 0; p->next && j < i-1; j++)
		p = p->next;
	if(!(p->next) || j > i-1)
		exit(ERROR);
	q = p->next;
	p->next = q->next;
	t = q->data;
	free(q);
	return t;
}

Status LList::ListTraverse(void (*func)(ElemType))
{
	for(int i = 1; i <= this->ListLength(); i++)
		(*func)(this->GetElem(i));
	return OK;
}
